In the age of cloud computing, data and computation are increasingly outsourced to cloud providers and therefore reliable cloud storage solutions are receiving unprecedented attention. For example by relying on a single cloud storage provider this may have disastrous consequences if the data is lost. The spectrum of problems leading to data loss and loss of availability ranges from power outages in data centers to corruption of the data, to bankruptcy of a data service company, etc.
One conventional cloud storage service is, for example, Amazon S3 providing an object store with basic write (object) and read (object) functionality. However, one of the drawbacks is that to build a reliable read/write object from a plurality of unreliable read/write objects requires storage proportional to the total number of clients in the underlying system. For example, in the non-patent literature Robert Haas, Alessandro Sorniotti, Marko Vukolic and Ido Zachevsky: Robust Data Sharing with Key-Value Stores. DSN 2012 an atomic object store is disclosed building top of a collection of key value stores application programmable interfaces that—besides write/read operations—have an additional list functionality providing an atomic snapshot of all keys in the key value store. However, one of the drawbacks is that in the worst case, the space complexity is proportional to the number of clients.
An increasing number of cloud storage services have also started providing besides read and (blind) writes also so-called conditional writes, for example provided by the Amazon Simple Database, Windows Azure Blob Storage, Google Storage, etc. These conditional writes are a mechanism for optimistic concurrency control in distributed systems and can be used for instance to prevent lost updates.